package com.lun.medium;

import java.util.ArrayList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class BalanceABinarySearchTree {
	
    public TreeNode balanceBST(TreeNode root) {
		List<TreeNode> list = new ArrayList<>();
		inorderTraverse(root, list);
    	return remakeBST(list, 0, list.size() - 1);
    }
        
    private void inorderTraverse(TreeNode node, List<TreeNode> list) {
    	if(node == null) return;
    	inorderTraverse(node.left, list);
    	list.add(node);
    	inorderTraverse(node.right, list);
    }
    
    private TreeNode remakeBST(List<TreeNode> list, int start, int end) {
    	if(start > end) return null;
    	int mid = start + (end - start) / 2;
    	TreeNode node = list.get(mid);
    	node.left = remakeBST(list, start, mid - 1);
    	node.right = remakeBST(list, mid + 1, end);
    	return node;
    }
    
}
